package sort;

/**
 * 这是一个整形数组的插入排序
 * @author lucky
 */
public class InsertionSort {
    /**
     * @param arr 这是一个整型数组
     * @return int[]
     */
    public static int[] insertionSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int j = i;//确定第二层循环的起始位置
            int temp = arr[i];//记录初始循环位置值，腾出空间后传
            while (j > 0 && temp < arr[j - 1]) {//必须满足两个条件循环才可以执行一次
                arr[j] = arr[j - 1];//把较大值直接往后面传递
                j--;
            }
            if (j!=i) {//排除相同值或者位置不变的情况以减小运算次数
                arr[j] = temp;//确定插入位置后将保存的值赋予确定的位置
            }
        }
        return arr;//返回排序过后的数组
    }
}
